{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Palindrome Permutation II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: generatePalindromes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #回文排列 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串 <code>s</code>&nbsp;，返回 <em>其重新排列组合后可能构成的所有回文字符串，并去除重复的组合</em>&nbsp;。</p>\n",
    "\n",
    "<p>你可以按 <strong>任意顺序</strong> 返回答案。如果&nbsp;<code>s</code>&nbsp;不能形成任何回文排列时，则返回一个空列表。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s = <code>\"aabb\"</code>\n",
    "<strong>输出: </strong><code>[\"abba\", \"baab\"]</code></pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s = <code>\"abc\"</code>\n",
    "<strong>输出: </strong><code>[]</code>\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" /></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 16</code></li>\n",
    "\t<li><code>s</code>&nbsp;仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [palindrome-permutation-ii](https://leetcode.cn/problems/palindrome-permutation-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [palindrome-permutation-ii](https://leetcode.cn/problems/palindrome-permutation-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aabb\"', '\"abc\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        counter = Counter(s)\n",
    "        odd_char = None\n",
    "        for c, v in counter.items():\n",
    "            if v % 2 != 0:\n",
    "                if odd_char is not None:\n",
    "                    return []\n",
    "                counter[c] -= 1\n",
    "                odd_char = c\n",
    "\n",
    "        half = len(s) // 2\n",
    "        ans = []\n",
    "        sofar = ''\n",
    "        def backtrack():\n",
    "            nonlocal sofar\n",
    "            if len(sofar) == half:\n",
    "                if odd_char:\n",
    "                    ans.append(sofar + odd_char + sofar[::-1])\n",
    "                else:\n",
    "                    ans.append(sofar + sofar[::-1])\n",
    "                return\n",
    "            for c, v in counter.items():\n",
    "                if v:\n",
    "                    counter[c] -= 2\n",
    "                    sofar += c\n",
    "                    backtrack()\n",
    "                    counter[c] += 2\n",
    "                    sofar = sofar[:-1]\n",
    "        backtrack()\n",
    "        return ans\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "\n",
    "        lookup = defaultdict(int)\n",
    "        for c in s:\n",
    "            lookup[c] += 1\n",
    "        \n",
    "        mid = \"\"\n",
    "        for c, cnt in lookup.items():\n",
    "            if cnt % 2 != 0:\n",
    "                if mid != \"\": # 已经有过奇数次的c了，再次出现，则不符合回文规则（只能有0个或1个奇数次出现的字符）\n",
    "                    return []\n",
    "                mid = c\n",
    "        \n",
    "        if mid != \"\":\n",
    "            lookup[mid] -= 1\n",
    "        \n",
    "        n = len(s)\n",
    "        res = []\n",
    "        def dfs(cur):\n",
    "            if len(cur) == n:\n",
    "                res.append(cur[:])\n",
    "            \n",
    "            for c, cnt in lookup.items():\n",
    "                if cnt > 0:\n",
    "                    lookup[c] -= 2\n",
    "                    dfs(c + cur + c)\n",
    "                    lookup[c] += 2\n",
    "        dfs(mid)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        # 使用 collections.Counter 统计字符串中每个字符的出现次数\n",
    "        h = collections.Counter(s)\n",
    "        # 记录奇数出现的次数\n",
    "        ji = 0\n",
    "        # 如果有奇数次字符，记录其中一个作为回文串的中心\n",
    "        mid = \"\"\n",
    "        # 要进行全排列的列表，去除了奇数次字符，将偶数次字符进行排列组合\n",
    "        list_s = []\n",
    "        for i, j in h.items():\n",
    "            if j % 2:\n",
    "                ji += 1\n",
    "                if ji >= 2:\n",
    "                    return []  # 如果奇数次字符超过1个，无法构成回文串，返回空列表\n",
    "                mid = i  # 记录奇数次字符作为中心字符\n",
    "            list_s.extend([i] * (j // 2))  # 将偶数次字符添加到排列列表中\n",
    "\n",
    "        # 回溯函数，用于生成回文字符串的全排列\n",
    "        def backtrace(s):\n",
    "            if s == []:\n",
    "                # 当排列列表为空时，构建回文串\n",
    "                huiwen = \"\".join(path)\n",
    "                huiwen += mid + huiwen[::-1]  # 添加中心字符并翻转左半部分\n",
    "                res.append(huiwen)  # 将生成的回文串添加到结果列表\n",
    "                return\n",
    "            for i in range(len(s)):\n",
    "                if i > 0 and s[i] == s[i - 1]:\n",
    "                    continue  # 跳过重复字符，避免生成重复的排列\n",
    "                path.append(s[i])\n",
    "                backtrace(s[:i] + s[i + 1:])  # 递归生成下一步的排列\n",
    "                path.pop()  # 回溯，移除最后添加的字符\n",
    "\n",
    "        res = []  # 存储结果的列表\n",
    "        path = []  # 记录当前路径的列表\n",
    "        backtrace(list_s)  # 调用回溯函数生成回文字符串的全排列\n",
    "        return res  # 返回结果列表\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        counter = collections.Counter(s)\n",
    "        odd_count= 0\n",
    "        odd_char = 0\n",
    "        for c, count in counter.items():\n",
    "            if count % 2 != 0:\n",
    "                odd_count += 1\n",
    "                odd_char = c\n",
    "            if odd_count > 1:\n",
    "                return []\n",
    "\n",
    "        mid = \"\"\n",
    "        if odd_count == 1:\n",
    "            mid += odd_char\n",
    "            counter[odd_char] -= 1\n",
    "\n",
    "        res = []\n",
    "\n",
    "        def dfs(cur, n):\n",
    "            if len(cur) > n: return\n",
    "            if len(cur) == n:\n",
    "                res.append(cur)\n",
    "                return \n",
    "\n",
    "            \n",
    "            for c, count in counter.items():\n",
    "                if count:\n",
    "                    counter[c] -= 2\n",
    "                    dfs(c + cur + c, n)\n",
    "                    counter[c] += 2\n",
    "\n",
    "\n",
    "        dfs(mid, len(s))\n",
    "        return res    \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # counter = collections.Counter(s)\n",
    "        # odd_count = 0\n",
    "        # odd_char = \"\"\n",
    "\n",
    "        # for c, count in counter.items():\n",
    "        #     if count % 2 != 0:\n",
    "        #         odd_char = c\n",
    "        #         odd_count += 1\n",
    "        #     if odd_count > 1:\n",
    "        #         return []\n",
    "        \n",
    "        # res = []\n",
    "        # mid = \"\"\n",
    "        # if odd_count == 1:\n",
    "        #     mid += odd_char\n",
    "        #     counter[odd_char] -= 1\n",
    "        \n",
    "\n",
    "        # def dfs(mid, n):\n",
    "        #     if len(mid) > n:\n",
    "        #         return\n",
    "            \n",
    "        #     if len(mid) == n:\n",
    "        #         res.append(mid)\n",
    "        #         return\n",
    "            \n",
    "        #     for c, count in counter.items():\n",
    "        #         if count:\n",
    "        #             counter[c] -= 2\n",
    "        #             dfs(c + mid + c, n)\n",
    "        #             counter[c] += 2\n",
    "        \n",
    "        # dfs(mid, len(s))\n",
    "        # return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    #     visited = [False] * len(s)\n",
    "    #     s = sorted(list(s))\n",
    "    #     res = []\n",
    "    #     self.dfs(s, visited, [], res)\n",
    "    #     return res\n",
    "    \n",
    "    # def dfs(self, s, visited, sub_res, res):\n",
    "    #     if len(sub_res) == len(s):\n",
    "    #         if self.is_palindrome(sub_res):\n",
    "    #             res.append(\"\".join(sub_res))\n",
    "    #             return\n",
    "        \n",
    "    #     for i in range(len(s)):\n",
    "    #         if visited[i]: continue\n",
    "    #         if i != 0 and s[i] == s[i - 1] and not visited[i - 1]:\n",
    "    #             continue\n",
    "\n",
    "    #         visited[i] = True\n",
    "    #         sub_res.append(s[i])\n",
    "    #         self.dfs(s, visited, sub_res, res)\n",
    "    #         visited[i] = False\n",
    "    #         sub_res.pop()\n",
    "        \n",
    "    # def is_palindrome(self, s):\n",
    "    #     left, right = 0, len(s) - 1\n",
    "    #     while left <= right:\n",
    "    #         if s[left] != s[right]:\n",
    "    #             return False\n",
    "    #         left += 1\n",
    "    #         right -= 1\n",
    "    #     return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        h = collections.Counter(s)\n",
    "        # 记录奇数出现的次数\n",
    "        ji = 0\n",
    "        # 如果有奇数次记录回文串中心\n",
    "        mid = \"\"\n",
    "        # 要进行全排列的列表\n",
    "        list_s = []\n",
    "        for i, j in h.items():\n",
    "            if j % 2:\n",
    "                ji += 1\n",
    "                if ji >= 2:\n",
    "                    return []\n",
    "                mid = i\n",
    "            list_s.extend([i]*(j//2))\n",
    "        # 全排列\n",
    "        # 例如 a, b, b\n",
    "        def backtrace(s):\n",
    "            if s == []:\n",
    "                huiwen = \"\".join(path)\n",
    "                huiwen +=  mid + huiwen[::-1]  \n",
    "                res.append(huiwen)\n",
    "                return\n",
    "            for i in range(len(s)):\n",
    "                if i > 0 and s[i] == s[i-1]:\n",
    "                    continue\n",
    "                path.append(s[i])\n",
    "                backtrace(s[:i]+s[i+1:])\n",
    "                path.pop()\n",
    "        res = []\n",
    "        path = []\n",
    "        backtrace(list_s)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        # 统计每个字符的出现次数\n",
    "        char_count = Counter(s)\n",
    "        \n",
    "        # 统计奇数次出现的字符个数\n",
    "        odd_count = sum(1 for count in char_count.values() if count % 2 == 1)\n",
    "        \n",
    "        # 如果存在多于一个奇数次出现的字符，无法构成回文排列，返回空列表\n",
    "        if odd_count > 1:\n",
    "            return []\n",
    "        \n",
    "        # 初始化回文排列的中间字符（如果存在奇数次出现的字符）\n",
    "        middle_char = \"\"\n",
    "        \n",
    "        for char, count in char_count.items():\n",
    "            # 如果字符出现次数是奇数，且还未设置中间字符，则将该字符设置为中间字符\n",
    "            if count % 2 == 1 and not middle_char:\n",
    "                middle_char = char\n",
    "        \n",
    "        def backtrack(path):\n",
    "            if len(path) == len(s):\n",
    "                result.append(\"\".join(path))\n",
    "                return\n",
    "            \n",
    "            for char, count in char_count.items():\n",
    "                if count > 0:\n",
    "                    char_count[char] -= 2\n",
    "                    path.append(char)\n",
    "                    path.insert(0, char)\n",
    "                    backtrack(path)\n",
    "                    path.pop()\n",
    "                    path.pop(0)\n",
    "                    char_count[char] += 2\n",
    "        \n",
    "        result = []\n",
    "        if middle_char:\n",
    "            char_count[middle_char] -= 1\n",
    "            backtrack([middle_char])\n",
    "        else:\n",
    "            backtrack([])\n",
    "        \n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import permutations\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        \"\"\"\n",
    "        >>> generatePalindromes(\"aabb\")\n",
    "        ['abba', 'baab']\n",
    "        >>> generatePalindromes('abc')\n",
    "        []\n",
    "        \"\"\"\n",
    "        counter = Counter()\n",
    "        for c in s:\n",
    "            counter[c] += 1\n",
    "        single_digit = None\n",
    "        for c in counter:\n",
    "            if counter[c] % 2 == 1:\n",
    "                if single_digit is not None:\n",
    "                    return []\n",
    "                single_digit = c\n",
    "        if single_digit:\n",
    "            counter[single_digit] -= 1\n",
    "        half_s = ''.join([c * (counter[c] // 2) for c in counter])\n",
    "        ret = set()\n",
    "        for p in permutations(half_s, len(half_s)):\n",
    "            p = ''.join(p)\n",
    "            if single_digit:\n",
    "                ret.add(f'{p}{single_digit}{\"\".join(reversed(p))}')\n",
    "            else:\n",
    "                ret.add(f'{p}{\"\".join(reversed(p))}')\n",
    "        return list(ret)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "\n",
    "        # palindromic permutation\n",
    "        # 出现次数应为even number （except at most one odd number appearance）\n",
    "        # 数据范围不超过16\n",
    "        counts = [0]*26\n",
    "        for c in s:\n",
    "            counts[ord(c)-ord(\"a\")] += 1\n",
    "        n = len(s)\n",
    "        odd = False\n",
    "        mid = \"\"\n",
    "        for i, x in enumerate(counts):\n",
    "            if x % 2 == 1:\n",
    "                if odd:\n",
    "                    return []\n",
    "                else:\n",
    "                    odd = True\n",
    "                    mid = chr(ord(\"a\")+i)\n",
    "                    counts[i] -= 1\n",
    "        if n == 1:\n",
    "            return [s]\n",
    "\n",
    "        res = []\n",
    "        used = [0]*26\n",
    "        def dfs(i,path):\n",
    "            # permutation [i:mid=n/2] 应填入什么\n",
    "            if i == n//2:\n",
    "                res.append(path+mid+path[::-1])\n",
    "                return\n",
    "\n",
    "            #枚举第i为可以填入的数字\n",
    "            for k in range(26):\n",
    "                if used[k] < counts[k]:\n",
    "                    used[k] += 2\n",
    "                    ch = chr(ord(\"a\")+k)\n",
    "                    dfs(i+1, path+ch)\n",
    "                    used[k] -= 2\n",
    "        dfs(0,\"\")\n",
    "        return res\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        h = collections.Counter(s)\n",
    "        # 记录奇数出现的次数\n",
    "        ji = 0\n",
    "        # 如果有奇数次记录回文串中心\n",
    "        mid = \"\"\n",
    "        # 要进行全排列的列表\n",
    "        list_s = []\n",
    "        for i, j in h.items():\n",
    "            if j % 2:\n",
    "                ji += 1\n",
    "                if ji >= 2:\n",
    "                    return []\n",
    "                mid = i\n",
    "            list_s.extend([i]*(j//2))\n",
    "        # 全排列\n",
    "        # 例如 a, b, b\n",
    "        def backtrace(s):\n",
    "            if s == []:\n",
    "                huiwen = \"\".join(path)\n",
    "                huiwen +=  mid + huiwen[::-1]  \n",
    "                res.append(huiwen)\n",
    "                return\n",
    "            for i in range(len(s)):\n",
    "                if i > 0 and s[i] == s[i-1]:\n",
    "                    continue\n",
    "                path.append(s[i])\n",
    "                backtrace(s[:i]+s[i+1:])\n",
    "                path.pop()\n",
    "        res = []\n",
    "        path = []\n",
    "        backtrace(list_s)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        ct, t, mid = Counter(s), '', ''\n",
    "        for x in ct:\n",
    "            if ct[x] & 1:\n",
    "                if mid:\n",
    "                    return []\n",
    "                mid = x\n",
    "            t += x * (ct[x] // 2)\n",
    "        return [*{x + mid + x[::-1] for x in map(''.join, permutations(t))}]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "\n",
    "        # palindromic permutation\n",
    "        # 出现次数应为even number （except at most one odd number appearance）\n",
    "        # 数据范围不超过16\n",
    "        counts = [0]*26\n",
    "        for c in s:\n",
    "            counts[ord(c)-ord(\"a\")] += 1\n",
    "        n = len(s)\n",
    "        odd = False\n",
    "        mid = \"\"\n",
    "        for i, x in enumerate(counts):\n",
    "            if x % 2 == 1:\n",
    "                if odd:\n",
    "                    return []\n",
    "                else:\n",
    "                    odd = True\n",
    "                    mid = chr(ord(\"a\")+i)\n",
    "                    counts[i] -= 1\n",
    "        if n == 1:\n",
    "            return [s]\n",
    "\n",
    "        res = []\n",
    "        used = [0]*26\n",
    "        def dfs(i,path):\n",
    "            # permutation [i:mid=n/2] 应填入什么\n",
    "            if i == n//2:\n",
    "                res.append(path+mid+path[::-1])\n",
    "                return\n",
    "\n",
    "            #枚举第i为可以填入的数字\n",
    "            for k in range(26):\n",
    "                if used[k] < counts[k]:\n",
    "                    used[k] += 2\n",
    "                    ch = chr(ord(\"a\")+k)\n",
    "                    dfs(i+1, path+ch)\n",
    "                    used[k] -= 2\n",
    "        dfs(0,\"\")\n",
    "        return res\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        res = []\n",
    "        path = \"\"\n",
    "        odd_cnt = 0\n",
    "        odd_letter = \"#\"\n",
    "        n = len(s)\n",
    "        letter_dict = defaultdict(int)\n",
    "        for c in s:\n",
    "            letter_dict[c] += 1\n",
    "        for letter in letter_dict:\n",
    "            if letter_dict[letter] % 2 == 1:\n",
    "                if not odd_cnt:\n",
    "                    odd_cnt += 1\n",
    "                    #odd_letter = letter\n",
    "                    path += letter\n",
    "                    letter_dict[letter] -= 1\n",
    "                else:\n",
    "                    return []\n",
    "        \n",
    "        def dfs(tmp, count):\n",
    "            if count == n:\n",
    "                res.append(tmp)\n",
    "                return\n",
    "            for letter, freq in letter_dict.items():\n",
    "                if freq > 0:\n",
    "                    letter_dict[letter] -= 2\n",
    "                    dfs(letter + tmp + letter, count + 2)\n",
    "                    letter_dict[letter] += 2\n",
    "        dfs(path, odd_cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        # 统计每个字符的出现次数\n",
    "        char_count = Counter(s)\n",
    "        \n",
    "        # 统计奇数次出现的字符个数\n",
    "        odd_count = sum(1 for count in char_count.values() if count % 2 == 1)\n",
    "        \n",
    "        # 如果存在多于一个奇数次出现的字符，无法构成回文排列，返回空列表\n",
    "        if odd_count > 1:\n",
    "            return []\n",
    "        \n",
    "        # 初始化回文排列的中间字符（如果存在奇数次出现的字符）\n",
    "        middle_char = \"\"\n",
    "        \n",
    "        for char, count in char_count.items():\n",
    "            # 如果字符出现次数是奇数，且还未设置中间字符，则将该字符设置为中间字符\n",
    "            if count % 2 == 1 and not middle_char:\n",
    "                middle_char = char\n",
    "        \n",
    "        def backtrack(path):\n",
    "            if len(path) == len(s):\n",
    "                result.append(\"\".join(path))\n",
    "                return\n",
    "            \n",
    "            for char, count in char_count.items():\n",
    "                if count > 0:\n",
    "                    char_count[char] -= 2\n",
    "                    path.append(char)\n",
    "                    path.insert(0, char)\n",
    "                    backtrack(path)\n",
    "                    path.pop()\n",
    "                    path.pop(0)\n",
    "                    char_count[char] += 2\n",
    "        \n",
    "        result = []\n",
    "        if middle_char:\n",
    "            char_count[middle_char] -= 1\n",
    "            backtrack([middle_char])\n",
    "        else:\n",
    "            backtrack([])\n",
    "        \n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def generatePalindromes(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        self.hashmap = collections.Counter(s)\n",
    "        # 出现奇数次的元素\n",
    "        self.odd = 0\n",
    "        self.res = []\n",
    "        for count in self.hashmap.values():\n",
    "            if count % 2 == 1:\n",
    "                self.odd += 1\n",
    "        \n",
    "        # 假如说字符串里出现奇数次的元素大于1，说明就不能用于构成回文串了\n",
    "        if self.odd > 1:\n",
    "            return []\n",
    "        \n",
    "        temp = \"\"\n",
    "        # 假如说存在奇数次元素，那么把它放在中间\n",
    "        for key in self.hashmap:\n",
    "            if self.hashmap[key] % 2 == 1:\n",
    "                temp += key\n",
    "                self.hashmap[key] -= 1\n",
    "        \n",
    "        # 进行回溯\n",
    "        self.helper(temp, len(s))\n",
    "        return self.res\n",
    "\n",
    "    def helper(self, temp, n):\n",
    "        if len(temp) > n:\n",
    "            return \n",
    "\n",
    "        if len(temp) == n:\n",
    "            self.res.append(temp[:])\n",
    "        \n",
    "        # 在这里我们构造回文串，进行回溯\n",
    "        for key in self.hashmap: ### 大循环保证顺序，\n",
    "            if self.hashmap[key] > 1:\n",
    "                self.hashmap[key] -= 2 ### 相当于做标记，下一次循环就不会再选取这个东西\n",
    "                self.helper(key + temp + key, n)\n",
    "                self.hashmap[key] += 2 ### 恢复现场！！ 相当于撤回\n",
    "        ### temp不pop怎么装东西！！！ 它并没有往里面装东西\n",
    "        \n",
    "        return \n",
    "    #### 回文，只能往两边加\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        char_num=Counter(s)\n",
    "        ct=0\n",
    "        mid=''\n",
    "        for key,val in char_num.items():\n",
    "            if val%2==1 and ct==0:\n",
    "                mid=key\n",
    "                char_num[key]-=1\n",
    "                ct+=1\n",
    "            elif val%2==1 and ct==1:\n",
    "                return []\n",
    "        if char_num[mid]==0 and mid!='':\n",
    "            char_num.pop(mid)\n",
    "        ret=list()\n",
    "        def get_word(char_num,word):\n",
    "            if len(char_num)==0:\n",
    "                ret.append(word)\n",
    "            for key in char_num:\n",
    "                temp=char_num.copy()\n",
    "                temp[key]-=2\n",
    "                if temp[key]==0:\n",
    "                    temp.pop(key)\n",
    "                get_word(temp,word+key)\n",
    "        get_word(char_num,'')\n",
    "        ret=list(ret)\n",
    "        for i in range(len(ret)):\n",
    "            ret[i]=ret[i][::-1]+mid+ret[i]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def generatePalindromes(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        self.hashmap = collections.Counter(s)\n",
    "        # 出现奇数次的元素\n",
    "        self.odd = 0\n",
    "        self.res = []\n",
    "        for count in self.hashmap.values():\n",
    "            if count % 2 == 1:\n",
    "                self.odd += 1\n",
    "        \n",
    "        # 假如说字符串里出现奇数次的元素大于1，说明就不能用于构成回文串了\n",
    "        if self.odd > 1:\n",
    "            return []\n",
    "        \n",
    "        temp = \"\"\n",
    "        # 假如说存在奇数次元素，那么把它放在中间\n",
    "        for key in self.hashmap:\n",
    "            if self.hashmap[key] % 2 == 1:\n",
    "                temp += key\n",
    "                self.hashmap[key] -= 1\n",
    "        \n",
    "        # 进行回溯\n",
    "        self.helper(temp, len(s))\n",
    "        return self.res\n",
    "\n",
    "    def helper(self, temp, n):\n",
    "        if len(temp) > n:\n",
    "            return \n",
    "\n",
    "        if len(temp) == n:\n",
    "            self.res.append(temp[:])\n",
    "        \n",
    "        # 在这里我们构造回文串，进行回溯\n",
    "        for key in self.hashmap: ### 大循环保证顺序，\n",
    "            if self.hashmap[key] > 1:\n",
    "                self.hashmap[key] -= 2 ### 相当于做标记，下一次循环就不会再选取这个东西\n",
    "                self.helper(key + temp + key, n)\n",
    "                self.hashmap[key] += 2 ### 恢复现场！！ 相当于撤回\n",
    "        ### temp不pop怎么装东西！！！ 它并没有往里面装东西\n",
    "        \n",
    "        #return \n",
    "    #### 回文，只能往两边加\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        #\"\"\"\n",
    "        from collections import Counter\n",
    "\n",
    "        count = Counter(s)\n",
    "        check = 0\n",
    "        single = \"\"\n",
    "        slist = []\n",
    "        for key, val in count.items():\n",
    "            if val % 2 == 1:\n",
    "                check += 1\n",
    "                single = key\n",
    "                count[key] -= 1\n",
    "            else:\n",
    "                slist.extend([ key for _ in range(val // 2)])\n",
    "        \n",
    "        if check > 1:\n",
    "            return []\n",
    "\n",
    "        def dfs_backtrace(cur: str, target_len: int) -> None:\n",
    "            #if len(cur) > target_len:           #加上这句，就快很多。不知道为啥\n",
    "            #    return \n",
    "            if len(cur) == target_len:\n",
    "                self.res.append(cur[:])\n",
    "            for c,freq in count.items():\n",
    "                if freq > 0:\n",
    "                    count[c] -= 2\n",
    "                    dfs_backtrace(c + cur + c, target_len)\n",
    "                    count[c] += 2           #回溯 套路\n",
    "\n",
    "        self.res =[]\n",
    "        dfs_backtrace(single, len(s))\n",
    "        return self.res\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        char_freq = defaultdict(int)\n",
    "        for c in s:\n",
    "            char_freq[c] += 1\n",
    "        \n",
    "        odd_cnt = 0                 #出现频率为奇数的字母个数\n",
    "        odd_char = '#'              #频率为奇数次的那个字母\n",
    "        for c in char_freq.keys():\n",
    "            if char_freq[c] % 2 == 1:\n",
    "                odd_cnt += 1\n",
    "                odd_char = c\n",
    "                if odd_cnt > 1:     #只允许有一个出现奇数次的字母\n",
    "                    return []\n",
    "        mid = \"\"\n",
    "        if odd_cnt == 1:            #如果有一个出现奇数次的字母\n",
    "            mid += odd_char\n",
    "            char_freq[odd_char] -= 1\n",
    "        \n",
    "        self.res = []\n",
    "\n",
    "        def dfs_backtrace(cur: str, target_len: int) -> None:\n",
    "            if len(cur) > target_len:           #加上这句，就快很多。不知道为啥\n",
    "                return \n",
    "            if len(cur) == target_len:\n",
    "                self.res.append(cur[:])\n",
    "            for c,freq in char_freq.items():\n",
    "                if freq > 0:\n",
    "                    char_freq[c] -= 2\n",
    "                    dfs_backtrace(c + cur + c, target_len)\n",
    "                    char_freq[c] += 2           #回溯 套路\n",
    "\n",
    "        dfs_backtrace(mid, n)\n",
    "        return self.res\n",
    "        \"\"\"\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.path = []\n",
    "\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        # 只需将字符串\"截取一半\",对这一半做全排列，进而获得我们需要的回文串。\n",
    "        import collections\n",
    "        s_map = collections.Counter(s)\n",
    "        new_s = []\n",
    "        odd = 0\n",
    "        self.ch = \"\"\n",
    "        for key,count in s_map.items():\n",
    "            if count % 2==1:\n",
    "                odd += 1\n",
    "                self.ch = key\n",
    "                new_s.append(key*((count-1)//2))\n",
    "            else:\n",
    "                new_s.append(key*(count//2))\n",
    "        if odd > 1:\n",
    "            return []\n",
    "        new_s = \"\".join(sorted(new_s))\n",
    "        used = [0] * len(new_s)\n",
    "        self.backtrack(new_s,used)\n",
    "        return self.res\n",
    "    \n",
    "    def backtrack(self,s,used):\n",
    "        if len(self.path) == len(s):\n",
    "            # 判断是否是回文串\n",
    "            sub_str = \"\".join(self.path)\n",
    "            # if self.ishuiwei(sub_str):\n",
    "            reversed_str = sub_str[::-1]\n",
    "            res_str = sub_str + self.ch + reversed_str\n",
    "            self.res.append(res_str)\n",
    "            return\n",
    "        \n",
    "        for i in range(0,len(s)):\n",
    "            if used[i] == 1:\n",
    "                continue\n",
    "            if i>0 and s[i-1] == s[i] and used[i-1] == 0:\n",
    "                continue\n",
    "            self.path.append(s[i])\n",
    "            used[i] = 1\n",
    "            self.backtrack(s, used)\n",
    "            self.path.pop()\n",
    "            used[i] = 0\n",
    "        \n",
    "    def ishuiwei(self,s):\n",
    "        new_s = s[::-1]\n",
    "        if new_s == s:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        # start = 0\n",
    "        # end = len(s) - 1\n",
    "        # while start < end:\n",
    "        #     if s[start] == s[end]:\n",
    "        #         start += 1\n",
    "        #         end -= 1\n",
    "        #     else:\n",
    "        #         return False\n",
    "        # return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        counter = collections.Counter(s)\n",
    "        odd_count = 0\n",
    "        odd_char = \"\"\n",
    "        for c, count in counter.items():\n",
    "            if count % 2 != 0:\n",
    "                odd_count += 1\n",
    "                odd_char = c\n",
    "\n",
    "            if odd_count > 1:\n",
    "                return []\n",
    "        \n",
    "        res = []\n",
    "        mid = \"\"\n",
    "        if odd_count == 1:\n",
    "            mid = odd_char\n",
    "            counter[odd_char] -= 1\n",
    "        \n",
    "        def dfs(mid, n):\n",
    "            if len(mid) > n: return\n",
    "            if len(mid) == n:\n",
    "                res.append(mid)\n",
    "                return\n",
    "            \n",
    "            for c, count in counter.items():\n",
    "                if count:\n",
    "                    counter[c] -= 2\n",
    "                    dfs(c + mid + c, n)\n",
    "                    counter[c] += 2\n",
    "        \n",
    "\n",
    "        dfs(mid, len(s))\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # counter = collections.Counter(s)\n",
    "        # odd_count = 0\n",
    "        # odd_char = \"\"\n",
    "\n",
    "        # for c, count in counter.items():\n",
    "        #     if count % 2 != 0:\n",
    "        #         odd_char = c\n",
    "        #         odd_count += 1\n",
    "        #     if odd_count > 1:\n",
    "        #         return []\n",
    "        \n",
    "        # res = []\n",
    "        # mid = \"\"\n",
    "        # if odd_count == 1:\n",
    "        #     mid += odd_char\n",
    "        #     counter[odd_char] -= 1\n",
    "        \n",
    "\n",
    "        # def dfs(mid, n):\n",
    "        #     if len(mid) > n:\n",
    "        #         return\n",
    "            \n",
    "        #     if len(mid) == n:\n",
    "        #         res.append(mid)\n",
    "        #         return\n",
    "            \n",
    "        #     for c, count in counter.items():\n",
    "        #         if count:\n",
    "        #             counter[c] -= 2\n",
    "        #             dfs(c + mid + c, n)\n",
    "        #             counter[c] += 2\n",
    "        \n",
    "        # dfs(mid, len(s))\n",
    "        # return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    #     visited = [False] * len(s)\n",
    "    #     s = sorted(list(s))\n",
    "    #     res = []\n",
    "    #     self.dfs(s, visited, [], res)\n",
    "    #     return res\n",
    "    \n",
    "    # def dfs(self, s, visited, sub_res, res):\n",
    "    #     if len(sub_res) == len(s):\n",
    "    #         if self.is_palindrome(sub_res):\n",
    "    #             res.append(\"\".join(sub_res))\n",
    "    #             return\n",
    "        \n",
    "    #     for i in range(len(s)):\n",
    "    #         if visited[i]: continue\n",
    "    #         if i != 0 and s[i] == s[i - 1] and not visited[i - 1]:\n",
    "    #             continue\n",
    "\n",
    "    #         visited[i] = True\n",
    "    #         sub_res.append(s[i])\n",
    "    #         self.dfs(s, visited, sub_res, res)\n",
    "    #         visited[i] = False\n",
    "    #         sub_res.pop()\n",
    "        \n",
    "    # def is_palindrome(self, s):\n",
    "    #     left, right = 0, len(s) - 1\n",
    "    #     while left <= right:\n",
    "    #         if s[left] != s[right]:\n",
    "    #             return False\n",
    "    #         left += 1\n",
    "    #         right -= 1\n",
    "    #     return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        counter = collections.Counter(s)\n",
    "        odd_count = 0\n",
    "        odd_char = \"\"\n",
    "        for c, count in counter.items():\n",
    "            if count % 2 != 0:\n",
    "                odd_count += 1\n",
    "                odd_char = c\n",
    "            if odd_count > 1:\n",
    "                return []\n",
    "        \n",
    "        res = []\n",
    "        mid = \"\"\n",
    "        if odd_count == 1:\n",
    "            mid = odd_char\n",
    "            counter[mid] -= 1\n",
    "        \n",
    "        def dfs(mid, n):\n",
    "            if len(mid) > n: return\n",
    "            if len(mid) == n:\n",
    "                res.append(mid)\n",
    "                return\n",
    "            \n",
    "            for c, count in counter.items():\n",
    "                if count:\n",
    "                    counter[c] -= 2\n",
    "                    dfs(c + mid + c, n)\n",
    "                    counter[c] += 2\n",
    "        \n",
    "\n",
    "\n",
    "        dfs(mid, len(s))\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # counter = collections.Counter(s)\n",
    "        # odd_count = 0\n",
    "        # odd_char = \"\"\n",
    "\n",
    "        # for c, count in counter.items():\n",
    "        #     if count % 2 != 0:\n",
    "        #         odd_char = c\n",
    "        #         odd_count += 1\n",
    "        #     if odd_count > 1:\n",
    "        #         return []\n",
    "        \n",
    "        # res = []\n",
    "        # mid = \"\"\n",
    "        # if odd_count == 1:\n",
    "        #     mid += odd_char\n",
    "        #     counter[odd_char] -= 1\n",
    "        \n",
    "\n",
    "        # def dfs(mid, n):\n",
    "        #     if len(mid) > n:\n",
    "        #         return\n",
    "            \n",
    "        #     if len(mid) == n:\n",
    "        #         res.append(mid)\n",
    "        #         return\n",
    "            \n",
    "        #     for c, count in counter.items():\n",
    "        #         if count:\n",
    "        #             counter[c] -= 2\n",
    "        #             dfs(c + mid + c, n)\n",
    "        #             counter[c] += 2\n",
    "        \n",
    "        # dfs(mid, len(s))\n",
    "        # return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    #     visited = [False] * len(s)\n",
    "    #     s = sorted(list(s))\n",
    "    #     res = []\n",
    "    #     self.dfs(s, visited, [], res)\n",
    "    #     return res\n",
    "    \n",
    "    # def dfs(self, s, visited, sub_res, res):\n",
    "    #     if len(sub_res) == len(s):\n",
    "    #         if self.is_palindrome(sub_res):\n",
    "    #             res.append(\"\".join(sub_res))\n",
    "    #             return\n",
    "        \n",
    "    #     for i in range(len(s)):\n",
    "    #         if visited[i]: continue\n",
    "    #         if i != 0 and s[i] == s[i - 1] and not visited[i - 1]:\n",
    "    #             continue\n",
    "\n",
    "    #         visited[i] = True\n",
    "    #         sub_res.append(s[i])\n",
    "    #         self.dfs(s, visited, sub_res, res)\n",
    "    #         visited[i] = False\n",
    "    #         sub_res.pop()\n",
    "        \n",
    "    # def is_palindrome(self, s):\n",
    "    #     left, right = 0, len(s) - 1\n",
    "    #     while left <= right:\n",
    "    #         if s[left] != s[right]:\n",
    "    #             return False\n",
    "    #         left += 1\n",
    "    #         right -= 1\n",
    "    #     return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        visited = Counter(s)\n",
    "        n = len(s)\n",
    "        if n % 2 == 0:\n",
    "            for value in visited.values():\n",
    "                if value == 1:\n",
    "                    return []\n",
    "            path = ['']*(n//2)\n",
    "        else:\n",
    "            cnt = 0\n",
    "            for key,value in visited.items():\n",
    "                if value % 2 != 0:\n",
    "                    cnt += 1\n",
    "                    path = ['']*(n//2+1)\n",
    "                    path[int(n//2)] = key\n",
    "                    visited[key] -= 1\n",
    "                if cnt > 1:\n",
    "                    return []\n",
    "        s = set(s)\n",
    "        ans = []\n",
    "        def dfs(index):\n",
    "            if index == n//2:\n",
    "                if n % 2 == 0:\n",
    "                    ans.append(''.join(path+path[::-1]))\n",
    "                else:\n",
    "                    ans.append(''.join(path+path[0:-1][::-1]))\n",
    "                return \n",
    "            for x in s:\n",
    "                if visited[x] == 0:\n",
    "                    continue\n",
    "                path[index] = x\n",
    "                visited[x] -= 2\n",
    "                dfs(index+1)\n",
    "                path[index] = ''\n",
    "                visited[x] += 2\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        #\"\"\"\n",
    "        from collections import Counter\n",
    "\n",
    "        count = Counter(s)\n",
    "        check = 0\n",
    "        single = \"\"\n",
    "        slist = []\n",
    "        for key, val in count.items():\n",
    "            if val % 2 == 1:\n",
    "                check += 1\n",
    "                single = key\n",
    "                count[key] -= 1\n",
    "            else:\n",
    "                slist.extend([ key for _ in range(val // 2)])\n",
    "        \n",
    "        if check > 1:\n",
    "            return []\n",
    "\n",
    "        def dfs_backtrace(cur: str, target_len: int) -> None:\n",
    "            if len(cur) > target_len:           #加上这句，就快很多。不知道为啥\n",
    "                return \n",
    "            if len(cur) == target_len:\n",
    "                self.res.append(cur[:])\n",
    "            for c,freq in count.items():\n",
    "                if freq > 0:\n",
    "                    count[c] -= 2\n",
    "                    dfs_backtrace(c + cur + c, target_len)\n",
    "                    count[c] += 2           #回溯 套路\n",
    "\n",
    "        self.res =[]\n",
    "        dfs_backtrace(single, len(s))\n",
    "        return self.res\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        char_freq = defaultdict(int)\n",
    "        for c in s:\n",
    "            char_freq[c] += 1\n",
    "        \n",
    "        odd_cnt = 0                 #出现频率为奇数的字母个数\n",
    "        odd_char = '#'              #频率为奇数次的那个字母\n",
    "        for c in char_freq.keys():\n",
    "            if char_freq[c] % 2 == 1:\n",
    "                odd_cnt += 1\n",
    "                odd_char = c\n",
    "                if odd_cnt > 1:     #只允许有一个出现奇数次的字母\n",
    "                    return []\n",
    "        mid = \"\"\n",
    "        if odd_cnt == 1:            #如果有一个出现奇数次的字母\n",
    "            mid += odd_char\n",
    "            char_freq[odd_char] -= 1\n",
    "        \n",
    "        self.res = []\n",
    "\n",
    "        def dfs_backtrace(cur: str, target_len: int) -> None:\n",
    "            if len(cur) > target_len:           #加上这句，就快很多。不知道为啥\n",
    "                return \n",
    "            if len(cur) == target_len:\n",
    "                self.res.append(cur[:])\n",
    "            for c,freq in char_freq.items():\n",
    "                if freq > 0:\n",
    "                    char_freq[c] -= 2\n",
    "                    dfs_backtrace(c + cur + c, target_len)\n",
    "                    char_freq[c] += 2           #回溯 套路\n",
    "\n",
    "        dfs_backtrace(mid, n)\n",
    "        return self.res\n",
    "        \"\"\"\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "\n",
    "        lookup = defaultdict(int)\n",
    "        for c in s:\n",
    "            lookup[c] += 1\n",
    "        \n",
    "        mid = \"\"\n",
    "        for c, cnt in lookup.items():\n",
    "            if cnt % 2 != 0:\n",
    "                if mid != \"\": # 已经有过奇数次的c了，再次出现，则不符合回文规则（只能有0个或1个奇数次出现的字符）\n",
    "                    return []\n",
    "                mid = c\n",
    "        \n",
    "        if mid != \"\":\n",
    "            lookup[mid] -= 1\n",
    "        \n",
    "        n = len(s)\n",
    "        res = []\n",
    "        def dfs(cur):\n",
    "            if len(cur) == n:\n",
    "                res.append(cur[:])\n",
    "                return\n",
    "            \n",
    "            for c, cnt in lookup.items():\n",
    "                if cnt > 0:\n",
    "                    lookup[c] -= 2\n",
    "                    dfs(c + cur + c)\n",
    "                    lookup[c] += 2\n",
    "        dfs(mid)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        counter = collections.Counter(s)\n",
    "        odd_count= 0\n",
    "        odd_char = \"\"\n",
    "        for c, count in counter.items():\n",
    "            if count % 2 != 0:\n",
    "                odd_count += 1\n",
    "                odd_char = c\n",
    "            if odd_count > 1:\n",
    "                return []\n",
    "\n",
    "        mid = \"\"\n",
    "        if odd_count == 1:\n",
    "            mid += odd_char\n",
    "            counter[odd_char] -= 1\n",
    "\n",
    "        res = []\n",
    "\n",
    "        def dfs(cur, n):\n",
    "            if len(cur) > n: return\n",
    "            if len(cur) == n:\n",
    "                res.append(cur)\n",
    "                return \n",
    "\n",
    "            \n",
    "            for c, count in counter.items():\n",
    "                if count:\n",
    "                    counter[c] -= 2\n",
    "                    dfs(c + cur + c, n)\n",
    "                    counter[c] += 2\n",
    "\n",
    "\n",
    "        dfs(mid, len(s))\n",
    "        return res    \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # counter = collections.Counter(s)\n",
    "        # odd_count = 0\n",
    "        # odd_char = \"\"\n",
    "\n",
    "        # for c, count in counter.items():\n",
    "        #     if count % 2 != 0:\n",
    "        #         odd_char = c\n",
    "        #         odd_count += 1\n",
    "        #     if odd_count > 1:\n",
    "        #         return []\n",
    "        \n",
    "        # res = []\n",
    "        # mid = \"\"\n",
    "        # if odd_count == 1:\n",
    "        #     mid += odd_char\n",
    "        #     counter[odd_char] -= 1\n",
    "        \n",
    "\n",
    "        # def dfs(mid, n):\n",
    "        #     if len(mid) > n:\n",
    "        #         return\n",
    "            \n",
    "        #     if len(mid) == n:\n",
    "        #         res.append(mid)\n",
    "        #         return\n",
    "            \n",
    "        #     for c, count in counter.items():\n",
    "        #         if count:\n",
    "        #             counter[c] -= 2\n",
    "        #             dfs(c + mid + c, n)\n",
    "        #             counter[c] += 2\n",
    "        \n",
    "        # dfs(mid, len(s))\n",
    "        # return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    #     visited = [False] * len(s)\n",
    "    #     s = sorted(list(s))\n",
    "    #     res = []\n",
    "    #     self.dfs(s, visited, [], res)\n",
    "    #     return res\n",
    "    \n",
    "    # def dfs(self, s, visited, sub_res, res):\n",
    "    #     if len(sub_res) == len(s):\n",
    "    #         if self.is_palindrome(sub_res):\n",
    "    #             res.append(\"\".join(sub_res))\n",
    "    #             return\n",
    "        \n",
    "    #     for i in range(len(s)):\n",
    "    #         if visited[i]: continue\n",
    "    #         if i != 0 and s[i] == s[i - 1] and not visited[i - 1]:\n",
    "    #             continue\n",
    "\n",
    "    #         visited[i] = True\n",
    "    #         sub_res.append(s[i])\n",
    "    #         self.dfs(s, visited, sub_res, res)\n",
    "    #         visited[i] = False\n",
    "    #         sub_res.pop()\n",
    "        \n",
    "    # def is_palindrome(self, s):\n",
    "    #     left, right = 0, len(s) - 1\n",
    "    #     while left <= right:\n",
    "    #         if s[left] != s[right]:\n",
    "    #             return False\n",
    "    #         left += 1\n",
    "    #         right -= 1\n",
    "    #     return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        h = collections.Counter(s)\n",
    "        # 记录奇数出现的次数\n",
    "        ji = 0\n",
    "        # 如果有奇数次记录回文串中心\n",
    "        mid = \"\"\n",
    "        # 要进行全排列的列表\n",
    "        list_s = []\n",
    "        for i, j in h.items():\n",
    "            if j % 2:\n",
    "                ji += 1\n",
    "                if ji >= 2:\n",
    "                    return []\n",
    "                mid = i\n",
    "            list_s.extend([i]*(j//2))\n",
    "        # 全排列\n",
    "        # 例如 a, b, b\n",
    "        def backtrace(s):\n",
    "            if s == []:\n",
    "                huiwen = \"\".join(path)\n",
    "                huiwen +=  mid + huiwen[::-1]  \n",
    "                res.append(huiwen)\n",
    "                return\n",
    "            for i in range(len(s)):\n",
    "                if i > 0 and s[i] == s[i-1]:\n",
    "                    continue\n",
    "                path.append(s[i])\n",
    "                backtrace(s[:i]+s[i+1:])\n",
    "                path.pop()\n",
    "        res = []\n",
    "        path = []\n",
    "        backtrace(list_s)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        \"\"\"\n",
    "        from collections import Counter\n",
    "\n",
    "        count = Counter(s)\n",
    "        check = 0\n",
    "        single = \"\"\n",
    "        slist = []\n",
    "        for key, val in count.items():\n",
    "            if val % 2 == 1:\n",
    "                check += 1\n",
    "                single = key\n",
    "            else:\n",
    "                slist.extend([ key for _ in range(val // 2)])\n",
    "        \n",
    "        if check > 1:\n",
    "            return []\n",
    "\n",
    "        def dfs_backtrace(cur: str, target_len: int) -> None:\n",
    "            if len(cur) > target_len:           #加上这句，就快很多。不知道为啥\n",
    "                return \n",
    "            if len(cur) == target_len:\n",
    "                self.res.append(cur[:])\n",
    "            for c,freq in count.items():\n",
    "                if freq > 0:\n",
    "                    count[c] -= 2\n",
    "                    dfs_backtrace(c + cur + c, target_len)\n",
    "                    count[c] += 2           #回溯 套路\n",
    "\n",
    "        self.res =[]\n",
    "        dfs_backtrace(single, len(s))\n",
    "        return self.res\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        char_freq = defaultdict(int)\n",
    "        for c in s:\n",
    "            char_freq[c] += 1\n",
    "        \n",
    "        odd_cnt = 0                 #出现频率为奇数的字母个数\n",
    "        odd_char = '#'              #频率为奇数次的那个字母\n",
    "        for c in char_freq.keys():\n",
    "            if char_freq[c] % 2 == 1:\n",
    "                odd_cnt += 1\n",
    "                odd_char = c\n",
    "                if odd_cnt > 1:     #只允许有一个出现奇数次的字母\n",
    "                    return []\n",
    "        mid = \"\"\n",
    "        if odd_cnt == 1:            #如果有一个出现奇数次的字母\n",
    "            mid += odd_char\n",
    "            char_freq[odd_char] -= 1\n",
    "        \n",
    "        self.res = []\n",
    "\n",
    "        def dfs_backtrace(cur: str, target_len: int) -> None:\n",
    "            if len(cur) > target_len:           #加上这句，就快很多。不知道为啥\n",
    "                return \n",
    "            if len(cur) == target_len:\n",
    "                self.res.append(cur[:])\n",
    "            for c,freq in char_freq.items():\n",
    "                if freq > 0:\n",
    "                    char_freq[c] -= 2\n",
    "                    dfs_backtrace(c + cur + c, target_len)\n",
    "                    char_freq[c] += 2           #回溯 套路\n",
    "\n",
    "        dfs_backtrace(mid, n)\n",
    "        return self.res\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        dic = collections.defaultdict(int)\n",
    "        for word in s:\n",
    "            dic[word] += 1\n",
    "        even = []\n",
    "        odd = None\n",
    "\n",
    "        for key,value in dic.items():\n",
    "            if value % 2 == 0:\n",
    "                for i in range(value // 2):\n",
    "                    even.append(key)\n",
    "            else:\n",
    "                if not odd: \n",
    "                    odd = key\n",
    "                    for i in range(value // 2):\n",
    "                        even.append(key)\n",
    "                else: return []\n",
    "        ans = []\n",
    "        \n",
    "        def recur(path,left,n):\n",
    "            if not left:\n",
    "                rev_path = list(reversed(path))\n",
    "                if odd:\n",
    "                    res = path + [odd] + rev_path\n",
    "                else:\n",
    "                    res = path + rev_path\n",
    "                res = ''.join(res)\n",
    "                if res not in ans:\n",
    "                    ans.append(res)\n",
    "                return\n",
    "            \n",
    "            for index,word in enumerate(left):\n",
    "                left.remove(word)\n",
    "                recur(path+[word],left,n)\n",
    "                left.insert(index, word)\n",
    "        \n",
    "        recur([],even,len(even))\n",
    "        return ans\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        counter = collections.Counter(s)\n",
    "        odd_count = 0\n",
    "        odd_char = \"\"\n",
    "\n",
    "        for c, count in counter.items():\n",
    "            if count % 2 != 0:\n",
    "                odd_char = c\n",
    "                odd_count += 1\n",
    "            if odd_count > 1:\n",
    "                return []\n",
    "        \n",
    "        res = []\n",
    "        mid = \"\"\n",
    "        if odd_count == 1:\n",
    "            mid += odd_char\n",
    "            counter[odd_char] -= 1\n",
    "        \n",
    "\n",
    "        def dfs(mid, n):\n",
    "            if len(mid) > n:\n",
    "                return\n",
    "            \n",
    "            if len(mid) == n:\n",
    "                res.append(mid)\n",
    "                return\n",
    "            \n",
    "            for c, count in counter.items():\n",
    "                if count:\n",
    "                    counter[c] -= 2\n",
    "                    dfs(c + mid + c, n)\n",
    "                    counter[c] += 2\n",
    "        \n",
    "        dfs(mid, len(s))\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    #     visited = [False] * len(s)\n",
    "    #     s = sorted(list(s))\n",
    "    #     res = []\n",
    "    #     self.dfs(s, visited, [], res)\n",
    "    #     return res\n",
    "    \n",
    "    # def dfs(self, s, visited, sub_res, res):\n",
    "    #     if len(sub_res) == len(s):\n",
    "    #         if self.is_palindrome(sub_res):\n",
    "    #             res.append(\"\".join(sub_res))\n",
    "    #             return\n",
    "        \n",
    "    #     for i in range(len(s)):\n",
    "    #         if visited[i]: continue\n",
    "    #         if i != 0 and s[i] == s[i - 1] and not visited[i - 1]:\n",
    "    #             continue\n",
    "\n",
    "    #         visited[i] = True\n",
    "    #         sub_res.append(s[i])\n",
    "    #         self.dfs(s, visited, sub_res, res)\n",
    "    #         visited[i] = False\n",
    "    #         sub_res.pop()\n",
    "        \n",
    "    # def is_palindrome(self, s):\n",
    "    #     left, right = 0, len(s) - 1\n",
    "    #     while left <= right:\n",
    "    #         if s[left] != s[right]:\n",
    "    #             return False\n",
    "    #         left += 1\n",
    "    #         right -= 1\n",
    "    #     return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def generatePalindromes(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        self.hashmap = collections.Counter(s)\n",
    "        # 出现奇数次的元素\n",
    "        self.odd = 0\n",
    "        self.res = []\n",
    "        for count in self.hashmap.values():\n",
    "            if count % 2 == 1:\n",
    "                self.odd += 1\n",
    "        \n",
    "        # 假如说字符串里出现奇数次的元素大于1，说明就不能用于构成回文串了\n",
    "        if self.odd > 1:\n",
    "            return []\n",
    "        \n",
    "        temp = \"\"\n",
    "        # 假如说存在奇数次元素，那么把它放在中间\n",
    "        for key in self.hashmap:\n",
    "            if self.hashmap[key] % 2 == 1:\n",
    "                temp += key\n",
    "                self.hashmap[key] -= 1\n",
    "        \n",
    "        # 进行回溯\n",
    "        self.helper(temp, len(s))\n",
    "        return self.res\n",
    "\n",
    "    def helper(self, temp, n):\n",
    "        if len(temp) > n:\n",
    "            return \n",
    "\n",
    "        if len(temp) == n:\n",
    "            self.res.append(temp[:])\n",
    "        \n",
    "        # 在这里我们构造回文串，进行回溯\n",
    "        for key in self.hashmap:\n",
    "            if self.hashmap[key] > 1:\n",
    "                self.hashmap[key] -= 2\n",
    "                self.helper(key + temp + key, n)\n",
    "                self.hashmap[key] += 2\n",
    "        \n",
    "        return \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "\n",
    "        lookup = defaultdict(int)\n",
    "        for c in s:\n",
    "            lookup[c] += 1\n",
    "        \n",
    "        mid = \"\"\n",
    "        for c, cnt in lookup.items():\n",
    "            if cnt % 2 != 0:\n",
    "                if mid != \"\": # 已经有过奇数次的c了，再次出现，则不符合回文规则（只能有0个或1个奇数次出现的字符）\n",
    "                    return []\n",
    "                mid = c\n",
    "        \n",
    "        if mid != \"\":\n",
    "            lookup[mid] -= 1\n",
    "        \n",
    "        n = len(s)\n",
    "        res = []\n",
    "        def dfs(cur):\n",
    "            if len(cur) == n:\n",
    "                res.append(cur[:])\n",
    "                return\n",
    "            \n",
    "            for c, cnt in lookup.items():\n",
    "                if cnt > 0:\n",
    "                    lookup[c] -= 2\n",
    "                    dfs(c + cur + c)\n",
    "                    lookup[c] += 2\n",
    "        dfs(mid)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        h=collections.Counter(s)\n",
    "        odd=0\n",
    "        mid=''\n",
    "        hal=[]\n",
    "        res=[]\n",
    "        path=[]\n",
    "        for k,c in h.items():\n",
    "            if c%2:\n",
    "                odd+=1\n",
    "                if odd>1:\n",
    "                    return []\n",
    "                mid=k\n",
    "            hal.extend([k]*(c//2))\n",
    "        def backtrace(hal):\n",
    "            if hal==[]:\n",
    "                res.append(''.join(path)+mid+''.join(path)[::-1])\n",
    "                return\n",
    "            for i in range(len(hal)):\n",
    "                if i>0 and hal[i]==hal[i-1]:\n",
    "                    continue\n",
    "                path.append(hal[i])\n",
    "                backtrace(hal[:i]+hal[i+1:])\n",
    "                path.pop()\n",
    "        backtrace(hal)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        letter_dict = {}\n",
    "        n = len(s)\n",
    "        ExistOdd = False\n",
    "        res = []\n",
    "        q = collections.deque()\n",
    "        cnt = 0\n",
    "        for c in s:\n",
    "            if c not in letter_dict:\n",
    "                letter_dict[c] = 1\n",
    "            else:\n",
    "                letter_dict[c] += 1\n",
    "        for letter in letter_dict:\n",
    "            if letter_dict[letter] % 2 == 1:\n",
    "                if not ExistOdd:\n",
    "                    ExistOdd = True\n",
    "                    letter_dict[letter] -= 1\n",
    "                    q.append(letter)\n",
    "                    cnt = 1\n",
    "                else:\n",
    "                    return []\n",
    "\n",
    "        def dfs(path, count: int):\n",
    "\n",
    "            if count == n:\n",
    "                tmp = \"\".join(list(path))\n",
    "                res.append(tmp)\n",
    "                return\n",
    "\n",
    "            for letter in letter_dict:\n",
    "                if letter_dict[letter] >= 2:\n",
    "                    path.append(letter)\n",
    "                    path.appendleft(letter)\n",
    "                    letter_dict[letter] -= 2\n",
    "                    dfs(path, count + 2)\n",
    "\n",
    "                    path.pop()\n",
    "                    path.popleft()\n",
    "                    letter_dict[letter] += 2\n",
    "\n",
    "        dfs(q, cnt)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        char_freq = defaultdict(int)\n",
    "        for c in s:\n",
    "            char_freq[c] += 1\n",
    "        \n",
    "        odd_cnt = 0                 #出现频率为奇数的字母个数\n",
    "        odd_char = '#'              #频率为奇数次的那个字母\n",
    "        for c in char_freq.keys():\n",
    "            if char_freq[c] % 2 == 1:\n",
    "                odd_cnt += 1\n",
    "                odd_char = c\n",
    "                if odd_cnt > 1:     #只允许有一个出现奇数次的字母\n",
    "                    return []\n",
    "        mid = \"\"\n",
    "        if odd_cnt == 1:            #如果有一个出现奇数次的字母\n",
    "            mid += odd_char\n",
    "            char_freq[odd_char] -= 1\n",
    "        \n",
    "        self.res = []\n",
    "\n",
    "        def dfs_backtrace(cur: str, target_len: int) -> None:\n",
    "            if len(cur) > target_len:           #加上这句，就快很多。不知道为啥\n",
    "                return \n",
    "            if len(cur) == target_len:\n",
    "                self.res.append(cur[:])\n",
    "            for c,freq in char_freq.items():\n",
    "                if freq > 0:\n",
    "                    char_freq[c] -= 2\n",
    "                    dfs_backtrace(c + cur + c, target_len)\n",
    "                    char_freq[c] += 2           #回溯 套路\n",
    "\n",
    "        dfs_backtrace(mid, n)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        dic = collections.defaultdict(int)\n",
    "\n",
    "        for ch in s:\n",
    "            dic[ch] += 1\n",
    "        mid = \"\"\n",
    "        candidates = []\n",
    "        n = len(s)\n",
    "        for k,v in dic.items():\n",
    "            if v & 1:\n",
    "                mid += k\n",
    "            for i in range(v//2):\n",
    "                candidates.append(k)\n",
    "            dic[k] = 0\n",
    "\n",
    "        if len(mid) > 1:\n",
    "            return []\n",
    "        res = []\n",
    "        candidates.sort()\n",
    "        # vis = set()\n",
    "        def perm(i):\n",
    "            if i == len(candidates):\n",
    "                res.append(\"\".join(candidates[::]) + mid + \"\".join(candidates[::-1]))\n",
    "            else:\n",
    "                \n",
    "                perm(i + 1)\n",
    "                vis = set()\n",
    "                for j in range(i + 1, n // 2):\n",
    "                    if candidates[j] != candidates[i] and candidates[j] != candidates[j - 1] and candidates[j] not in vis:\n",
    "                        candidates[i], candidates[j] = candidates[j], candidates[i]\n",
    "                        vis.add(candidates[i])\n",
    "                        perm(i + 1)\n",
    "                        candidates[i], candidates[j] = candidates[j], candidates[i]\n",
    "\n",
    "\n",
    "\n",
    "        perm(0)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        self.res = []\n",
    "        char_freq = defaultdict(int)\n",
    "        for s1 in s:\n",
    "            char_freq[s1] +=1\n",
    "        \n",
    "        odd_count = 0\n",
    "        odd_ch = '#'\n",
    "\n",
    "        for c in char_freq.keys():\n",
    "            if char_freq[c] % 2 == 1:\n",
    "                odd_count +=1\n",
    "                odd_ch = c\n",
    "                if odd_count > 1:\n",
    "                    return []\n",
    "        \n",
    "        mid  = \"\"\n",
    "        if odd_count == 1:\n",
    "            mid += odd_ch\n",
    "            char_freq[odd_ch] -=1\n",
    "        \n",
    "        def back(cur, target_l):\n",
    "            if len(cur) > target_l:\n",
    "                return\n",
    "            if len(cur) == target_l:\n",
    "                self.res.append(cur[:])\n",
    "            for c, freq in char_freq.items():\n",
    "                if freq > 0:\n",
    "                    char_freq[c]-=2\n",
    "                    back(c+cur+c, target_l)\n",
    "                    char_freq[c]+=2\n",
    "        \n",
    "        back(mid, len(s))\n",
    "        return self.res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        d = collections.defaultdict(int)\n",
    "        for i in s:\n",
    "            d[i] += 1\n",
    "        odd = []\n",
    "        pix = []\n",
    "        for k, v in d.items():\n",
    "            if v % 2 == 0:\n",
    "                pix += [k]*(v//2)\n",
    "            else:\n",
    "                odd.append(k)\n",
    "                pix += [k]*(v//2)\n",
    "        if len(odd) > 1:\n",
    "            return []\n",
    "\n",
    "        ans = ''\n",
    "        if odd:\n",
    "            ans += odd[0]\n",
    "        res = []\n",
    "        def dfs(pix, ans):\n",
    "            if not pix:\n",
    "                if ans not in res:\n",
    "                    res.append(ans)\n",
    "                return\n",
    "            for i in range(len(pix)):\n",
    "                dfs(pix[:i]+pix[i+1:], pix[i]+ans+pix[i])\n",
    "        dfs(pix, ans)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        res = []\n",
    "        n = len(s)\n",
    "        dic = collections.defaultdict(int)\n",
    "        for a in s:\n",
    "            dic[a] += 1\n",
    "\n",
    "        cnt_odd = 0\n",
    "        char_odd = None\n",
    "        for k, v in dic.items():\n",
    "            if v%2==1:\n",
    "                cnt_odd += 1\n",
    "                char_odd = k\n",
    "                if cnt_odd > 1:\n",
    "                    return []\n",
    "        seq = []\n",
    "        # if char_odd is not None:\n",
    "        #     seq.append(char_odd)\n",
    "        target_len = (n - cnt_odd) // 2\n",
    "        def helper():\n",
    "            if len(seq) == target_len:\n",
    "                str_seq = \"\"\n",
    "                if cnt_odd > 0:\n",
    "                    str_seq += char_odd\n",
    "                str1 = \"\".join(seq)\n",
    "                str2 = str1[::-1]\n",
    "                res.append(str2 + str_seq + str1)\n",
    "                return\n",
    "            for  k, v in dic.items():\n",
    "                if v < 2:\n",
    "                    continue\n",
    "                seq.append(k)\n",
    "                dic[k] -= 2\n",
    "                helper()\n",
    "                dic[k] += 2\n",
    "                seq.pop()\n",
    "\n",
    "        helper()\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        dic = collections.defaultdict(int)\n",
    "\n",
    "        for ch in s:\n",
    "            dic[ch] += 1\n",
    "        mid = \"\"\n",
    "        candidates = []\n",
    "        n = len(s)\n",
    "        for k,v in dic.items():\n",
    "            if v & 1:\n",
    "                mid += k\n",
    "            for i in range(v//2):\n",
    "                candidates.append(k)\n",
    "            dic[k] = 0\n",
    "\n",
    "        if len(mid) > 1:\n",
    "            return []\n",
    "        res = []\n",
    "        candidates.sort()\n",
    "        # vis = set()\n",
    "        def perm(i):\n",
    "            if i == len(candidates):\n",
    "                res.append(\"\".join(candidates[::]) + mid + \"\".join(candidates[::-1]))\n",
    "            else:\n",
    "                perm(i + 1)\n",
    "                vis = set()\n",
    "                for j in range(i + 1, n // 2):\n",
    "                    if candidates[j] != candidates[i] and candidates[j] not in vis:\n",
    "                        candidates[i], candidates[j] = candidates[j], candidates[i]\n",
    "                        vis.add(candidates[i])\n",
    "                        perm(i + 1)\n",
    "                        candidates[i], candidates[j] = candidates[j], candidates[i]\n",
    "\n",
    "\n",
    "        perm(0)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        #\"\"\"\n",
    "        from collections import Counter\n",
    "\n",
    "        count = Counter(s)\n",
    "        check = 0\n",
    "        single = \"\"\n",
    "        slist = []\n",
    "        for key, val in count.items():\n",
    "            if val % 2 == 1:\n",
    "                check += 1\n",
    "                single = key\n",
    "                count[key] -= 1\n",
    "            else:\n",
    "                slist.extend([ key for _ in range(val // 2)])\n",
    "        \n",
    "        if check > 1:\n",
    "            return []\n",
    "\n",
    "        def dfs_backtrace(cur: str, target_len: int) -> None:\n",
    "            #if len(cur) > target_len:           #加上这句，就快很多。不知道为啥\n",
    "            #    return \n",
    "            if len(cur) == target_len:\n",
    "                self.res.append(cur[:])\n",
    "            for c,freq in count.items():\n",
    "                if freq > 0:\n",
    "                    count[c] -= 2\n",
    "                    dfs_backtrace(c + cur + c, target_len)\n",
    "                    count[c] += 2           #回溯 套路\n",
    "\n",
    "        self.res =[]\n",
    "        dfs_backtrace(single, len(s))\n",
    "        return self.res\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        char_freq = defaultdict(int)\n",
    "        for c in s:\n",
    "            char_freq[c] += 1\n",
    "        \n",
    "        odd_cnt = 0                 #出现频率为奇数的字母个数\n",
    "        odd_char = '#'              #频率为奇数次的那个字母\n",
    "        for c in char_freq.keys():\n",
    "            if char_freq[c] % 2 == 1:\n",
    "                odd_cnt += 1\n",
    "                odd_char = c\n",
    "                if odd_cnt > 1:     #只允许有一个出现奇数次的字母\n",
    "                    return []\n",
    "        mid = \"\"\n",
    "        if odd_cnt == 1:            #如果有一个出现奇数次的字母\n",
    "            mid += odd_char\n",
    "            char_freq[odd_char] -= 1\n",
    "        \n",
    "        self.res = []\n",
    "\n",
    "        def dfs_backtrace(cur: str, target_len: int) -> None:\n",
    "            if len(cur) > target_len:           #加上这句，就快很多。不知道为啥\n",
    "                return \n",
    "            if len(cur) == target_len:\n",
    "                self.res.append(cur[:])\n",
    "            for c,freq in char_freq.items():\n",
    "                if freq > 0:\n",
    "                    char_freq[c] -= 2\n",
    "                    dfs_backtrace(c + cur + c, target_len)\n",
    "                    char_freq[c] += 2           #回溯 套路\n",
    "\n",
    "        dfs_backtrace(mid, n)\n",
    "        return self.res\n",
    "        \"\"\"\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# aabb\n",
    "# a:2\n",
    "# b:2\n",
    "# abba, baab, bbaa (no),\n",
    "\n",
    "# [] -> []\n",
    "\n",
    "# a -> a\n",
    "# aacbb -> c should be in the central, otherwise it will fails\n",
    "# aacbbddd\n",
    "# aacdbb \n",
    "# optimization\n",
    "# aabb, a:1, b:1 \n",
    "# aabbc, a:1, b:1, c:1, odd = \"c\"\n",
    "# ab, ba, \n",
    "from collections import defaultdict \n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        char_count = defaultdict(int)\n",
    "        for c in s:\n",
    "            char_count[c] += 1 \n",
    "        \n",
    "        # {a:2, b:2}\n",
    "        \n",
    "        # check if more than one odd count\n",
    "        is_odd = False \n",
    "        odd_c = None\n",
    "        for c in char_count:\n",
    "            if char_count[c] %2 == 1:\n",
    "                if is_odd:\n",
    "                    return []\n",
    "                else:\n",
    "                    is_odd = True \n",
    "                    odd_c = c \n",
    "\n",
    "        # is_odd  =False, \n",
    "        # divid those in count by 2 \n",
    "        # for odd, 1 // 2 = 0 ,3 //2 = 1\n",
    "        for c in char_count:\n",
    "            char_count[c] //=2 \n",
    "        \n",
    "        print(char_count)\n",
    "        # {a:1, b:1}, \n",
    "        res = []\n",
    "        path = \"\"\n",
    "        if is_odd:\n",
    "            # res.append()\n",
    "            path += odd_c\n",
    "            \n",
    "            self.backtrack(char_count, res,path, len(s)//2+1, is_odd) \n",
    "        else:\n",
    "            # print(len(s)//2)\n",
    "            self.backtrack(char_count,res, path, len(s)//2, is_odd) # {a:1, b:1},[], \"\", 2 \n",
    "        return res \n",
    "        \n",
    "    def backtrack(self, char_count,res,path,size, is_odd):\n",
    "        if len(path) == size:\n",
    "            # odd\n",
    "            if is_odd: \n",
    "                # print(\"path\", path[::-1])\n",
    "                path = path[1:][::-1] + path #baab\n",
    "                res.append(path)\n",
    "            # even \n",
    "            else:\n",
    "                # print(\"path\", path[::-1])\n",
    "                path = path[::-1] + path\n",
    "               \n",
    "                res.append(path)\n",
    "\n",
    "\n",
    "        for c in char_count:\n",
    "            if char_count[c] >0:\n",
    "                char_count[c] -= 1 \n",
    "            \n",
    "                self.backtrack(char_count,res,path+c,size,is_odd) # ab\n",
    "                char_count[c] += 1 \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        map=defaultdict(int)\n",
    "        for i in s:\n",
    "            map[i]+=1\n",
    "        n=len(s)\n",
    "        path=[]\n",
    "        res=[]\n",
    "        def dfs1(i,map):\n",
    "            if i==n/2:\n",
    "                t=\"\".join(path.copy())\n",
    "                t=t+t[::-1]\n",
    "                res.append(t)\n",
    "            if i<n/2:\n",
    "                for k in map:\n",
    "                    if map[k]>1:\n",
    "                        path.append(k)\n",
    "                        map[k]-=2\n",
    "                        dfs1(i+1,map)\n",
    "                        map[k]+=2\n",
    "                        path.pop()\n",
    "\n",
    "        def dfs2(i,map):\n",
    "            if i==n//2+1:\n",
    "                t1=path[:-1][::-1]\n",
    "                t=\"\".join(path)+\"\".join(t1)\n",
    "                res.append(t)\n",
    "            if i<n//2:\n",
    "                for k in map:\n",
    "                    if map[k]>1:\n",
    "                        print(k)\n",
    "                        path.append(k)\n",
    "                        print(path)\n",
    "                        map[k]-=2\n",
    "                        dfs2(i+1,map)\n",
    "                        map[k]+=2\n",
    "                        path.pop()\n",
    "            if i==n//2:\n",
    "                for k in map:\n",
    "                    if map[k]>0:\n",
    "                        path.append(k)\n",
    "                        map[k]-=1\n",
    "                        dfs2(i+1,map)\n",
    "                        map[k]+=1\n",
    "                        path.pop()\n",
    "\n",
    "        if n%2==0:\n",
    "            dfs1(0,map)\n",
    "        else:\n",
    "            dfs2(0,map)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.result = list()\n",
    "\n",
    "    def generatePalindromes(self, s: str) -> [str]:\n",
    "        if len(s) == 1:\n",
    "            return [s]\n",
    "        hashtable = [0 for i in range(26)]\n",
    "        flag = False\n",
    "        center = None\n",
    "        target_len=len(s)\n",
    "        for char in s:\n",
    "            hashtable[ord(char) - ord('a')] += 1\n",
    "        for idx, num in enumerate(hashtable):\n",
    "            if num % 2 == 1:\n",
    "                if flag:\n",
    "                    return []\n",
    "                flag = True\n",
    "                target_len-=1\n",
    "                center = self.get_char(idx)\n",
    "                hashtable[idx] -= 1\n",
    "        for idx in range(26):\n",
    "            if hashtable[idx] > 0:\n",
    "                self.dfs(hashtable, idx, [], center, flag, target_len)\n",
    "        return self.result\n",
    "\n",
    "    @staticmethod\n",
    "    def get_char(idx) -> chr:\n",
    "        return chr(idx + ord('a'))\n",
    "\n",
    "    # @staticmethod\n",
    "    def get_string(self, path):\n",
    "        string = \"\"\n",
    "        string=''.join([self.get_char(char) for char in path])\n",
    "        return string\n",
    "\n",
    "    def dfs(self, hashtable: [int], idx: int, path: [int], center: chr, center_flag: bool, target_len: int):\n",
    "        hashtable[idx] -= 2\n",
    "        path.append(idx)\n",
    "        if len(path) * 2 == target_len:\n",
    "            string = self.get_string(path)\n",
    "            left = string[::-1]\n",
    "            if center_flag:\n",
    "                self.result.append(left + center + string)\n",
    "            else:\n",
    "                self.result.append(left + string)\n",
    "        else:\n",
    "            for i in range(26):\n",
    "                if hashtable[i] > 0:\n",
    "                    self.dfs(hashtable, i, path, center, center_flag, target_len)\n",
    "        path.pop()\n",
    "        hashtable[idx] += 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        ans = []\n",
    "        cnt = Counter(s)\n",
    "        if n % 2:\n",
    "            odd = ''\n",
    "            for k, v in cnt.items():\n",
    "                if v % 2:\n",
    "                    if odd:\n",
    "                        return []\n",
    "                    else:\n",
    "                        odd = k \n",
    "            half = []\n",
    "            for k, v in cnt.items():\n",
    "                if v % 2:\n",
    "                    half.extend([k] * ((v - 1) // 2))\n",
    "                else:\n",
    "                    half.extend([k] * (v // 2))\n",
    "            for i in permutations(half, len(half)):\n",
    "                tmp = ''.join(i)\n",
    "                ans.append(tmp + odd + tmp[::-1])\n",
    "            return list(set(ans))\n",
    "        else:\n",
    "            for k, v in cnt.items():\n",
    "                if v % 2:\n",
    "                    return []\n",
    "            half = []\n",
    "            for k, v in cnt.items():\n",
    "                half.extend([k] * (v // 2))\n",
    "            for i in permutations(half, len(half)):\n",
    "                tmp = ''.join(i)\n",
    "                ans.append(tmp + tmp[::-1])\n",
    "            return list(set(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        alphas = defaultdict(int)\n",
    "\n",
    "        for o in s:\n",
    "            alphas[o] += 1\n",
    "\n",
    "        cnt = 0\n",
    "        ans = set()\n",
    "        c = \"\"\n",
    "        for k, v in alphas.items():\n",
    "            if v % 2 != 0:\n",
    "                cnt += 1\n",
    "                c = k\n",
    "\n",
    "            if cnt > 1:\n",
    "                return []\n",
    "\n",
    "        def dfs(target: str) -> None:\n",
    "            if len(target) == len(s):\n",
    "                ans.add(target)\n",
    "                return\n",
    "\n",
    "            for k1, v1 in alphas.items():\n",
    "                if v1 >= 2:\n",
    "                    alphas[k1] -= 2\n",
    "                    dfs(k1 + target + k1)\n",
    "                    alphas[k1] += 2\n",
    "\n",
    "        dfs(c)\n",
    "        return list(ans)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        # 回文串\n",
    "        cnt = Counter(s)\n",
    "        n = len(s)\n",
    "        if (n & 1) and sum(1 if (v & 1) else 0 for v in cnt.values()) > 1:\n",
    "            return []\n",
    "        ans = set()\n",
    "        def dfs(ele, l, r):\n",
    "            if l > r:\n",
    "                ans.add(''.join(ele))\n",
    "                return\n",
    "            for k, v in cnt.items():\n",
    "                if v:\n",
    "                    if l == r:\n",
    "                        ele[l] = k\n",
    "                        cnt[k] -= 1\n",
    "                        dfs(ele, l + 1, r - 1)\n",
    "                        cnt[k] += 1\n",
    "                    if v > 1 and l != r:\n",
    "                        ele[l] = k\n",
    "                        ele[r] = k\n",
    "                        cnt[k] -= 2\n",
    "                        dfs(ele, l + 1, r - 1)\n",
    "                        cnt[k] += 2\n",
    "        \n",
    "\n",
    "        dfs([None for _ in range(n)], 0, n - 1)\n",
    "        return list(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "\n",
    "        n=len(s)\n",
    "        c1=Counter(s)\n",
    "\n",
    "        # ??\n",
    "        odd = [c for c in c1 if c1[c]%2==1]\n",
    "\n",
    "        # edge case\n",
    "        for c in c1:\n",
    "            c1[c]=c1[c]//2\n",
    "        if len(odd)>1:\n",
    "            return []\n",
    "\n",
    "\n",
    "        # edge case\n",
    "        if n==1:\n",
    "            return list(s)\n",
    "\n",
    "        res = set()\n",
    "        def dfs(i, path):\n",
    "            if i == n//2:\n",
    "                # ??\n",
    "                res.add(\"\".join(path)+\"\".join(odd)+\"\".join(reversed(path)))\n",
    "                return\n",
    "            for c in c1:\n",
    "                if c1[c]:\n",
    "                    # ??\n",
    "                    c1[c]-=1\n",
    "                    path.append(c)\n",
    "                    dfs(i+1, path)\n",
    "                    path.pop()\n",
    "                    c1[c]+=1\n",
    "        \n",
    "        dfs(0, [])\n",
    "        return list(res)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "\n",
    "        n=len(s)\n",
    "        c1=Counter(s)\n",
    "\n",
    "        # ??\n",
    "        odd = [c for c in c1 if c1[c]%2==1]\n",
    "\n",
    "        # edge case\n",
    "        for c in c1:\n",
    "            c1[c]=c1[c]//2\n",
    "        if len(odd)>1:\n",
    "            return []\n",
    "\n",
    "\n",
    "        # edge case\n",
    "        if n==1:\n",
    "            return list(s)\n",
    "\n",
    "        res = set()\n",
    "        def dfs(i, path):\n",
    "            if i == n//2:\n",
    "                # ??\n",
    "                res.add(\"\".join(path)+\"\".join(odd)+\"\".join(reversed(path)))\n",
    "                return\n",
    "            for c in c1:\n",
    "                if c1[c] != 0:\n",
    "                    # ??\n",
    "                    c1[c]-=1\n",
    "                    path.append(c)\n",
    "                    dfs(i+1, path)\n",
    "                    path.pop()\n",
    "                    c1[c]+=1\n",
    "        \n",
    "        dfs(0, [])\n",
    "        return list(res)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        cnter = defaultdict(lambda: 0)\n",
    "\n",
    "        for item in s:\n",
    "            cnter[item] += 1\n",
    "        \n",
    "        one_cnt_keys = [key for key in cnter if cnter[key] % 2 == 1]\n",
    "        if len(one_cnt_keys) > 1:\n",
    "            return []\n",
    "        \n",
    "        if len(one_cnt_keys) == 1:\n",
    "            cnter[one_cnt_keys[0]] -= 1\n",
    "            mid = one_cnt_keys[0]\n",
    "        else:\n",
    "            mid = ''\n",
    "        \n",
    "        half_list = [char_item * (cnter[char_item] // 2) for char_item in cnter]\n",
    "        half_candidates = ''.join(half_list)\n",
    "\n",
    "        ret_list = []\n",
    "        used = [False] * len(half_candidates)\n",
    "        buffer = []\n",
    "\n",
    "        def bt():\n",
    "            if len(buffer) == len(half_candidates):\n",
    "                ret_list.append(''.join(buffer))\n",
    "                return\n",
    "\n",
    "            idx = 0\n",
    "            while idx < len(half_candidates):\n",
    "                if used[idx]:\n",
    "                    idx += 1\n",
    "                    continue\n",
    "                buffer.append(half_candidates[idx])\n",
    "                used[idx] = True\n",
    "                bt()\n",
    "                used[idx] = False\n",
    "                buffer.pop()\n",
    "                next_idx = idx\n",
    "                while next_idx < len(half_candidates) and half_candidates[next_idx] == half_candidates[idx]:\n",
    "                    next_idx += 1\n",
    "                idx = next_idx\n",
    "        \n",
    "        bt()\n",
    "        ret_list = [item + mid + item[:: -1] for item in ret_list]\n",
    "        return ret_list\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        char_num=Counter(s)\n",
    "        ct=0\n",
    "        mid=''\n",
    "        for key,val in char_num.items():\n",
    "            if val%2==1 and ct==0:\n",
    "                mid=key\n",
    "                char_num[key]-=1\n",
    "                ct+=1\n",
    "            elif val%2==1 and ct==1:\n",
    "                return []\n",
    "        if char_num[mid]==0 and mid!='':\n",
    "            char_num.pop(mid)\n",
    "        ret=set()\n",
    "        def get_word(char_num,word):\n",
    "            if len(char_num)==0:\n",
    "                ret.add(word)\n",
    "            for key in char_num:\n",
    "                temp=char_num.copy()\n",
    "                temp[key]-=2\n",
    "                if temp[key]==0:\n",
    "                    temp.pop(key)\n",
    "                get_word(temp,word+key)\n",
    "        get_word(char_num,'')\n",
    "        ret=list(ret)\n",
    "        for i in range(len(ret)):\n",
    "            ret[i]=ret[i][::-1]+mid+ret[i]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        visited=set()\n",
    "        def f(x):\n",
    "            if len(x)==len(ns):\n",
    "                ans.append(x[::])\n",
    "            for i in range(len(ns)):\n",
    "                if i not in visited:\n",
    "                    visited.add(i)\n",
    "                    f(x+ns[i])\n",
    "                    visited.remove(i)\n",
    "        dt=dict()\n",
    "        for i in s:\n",
    "            if i in dt:\n",
    "                dt[i]+=1\n",
    "            else:\n",
    "                dt[i]=1\n",
    "        c=0\n",
    "        cs1=''\n",
    "        ns=''\n",
    "        for key in dt.keys():\n",
    "            if dt[key]%2==1:\n",
    "                \n",
    "                c+=1\n",
    "                cs1=key\n",
    "                ns+=(dt[key]//2)*key\n",
    "            else:\n",
    "                ns+=(dt[key]//2)*key\n",
    "        print('ns',ns)\n",
    "        print('c',c)\n",
    "        if c>1:\n",
    "            return []\n",
    "        ans=[]\n",
    "        f('')\n",
    "        print(\"ans\",ans)\n",
    "        ans=list(set(ans))\n",
    "        for i in range(len(ans)):\n",
    "            ans[i]=ans[i]+cs1+ans[i][::-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def generatePalindromes(self, s: str) -> List[str]:\n",
    "        counts = collections.Counter(s)\n",
    "        half   = ''\n",
    "        middle = ''\n",
    "        for x in counts:\n",
    "            if counts[x] % 2 == 1:\n",
    "                if middle != '':\n",
    "                    return []\n",
    "                middle = x\n",
    "            half += (counts[x] // 2) * x\n",
    "        \n",
    "        half = list(half)\n",
    "        half.sort()\n",
    "\n",
    "        n = len(half)\n",
    "        half.sort()\n",
    "        seen   = [False] * n\n",
    "        answer = list()\n",
    "\n",
    "        def backtrace(i, path):\n",
    "            if i == n:\n",
    "                answer.append(path)\n",
    "            for j in range(n):\n",
    "                if j > 0 and half[j - 1] == half[j] and not seen[j - 1]:\n",
    "                    continue # 同层剪枝\n",
    "                if not seen[j]:\n",
    "                    seen[j] = True\n",
    "                    backtrace(i + 1, path + half[j])\n",
    "                    seen[j] = False\n",
    "        \n",
    "        backtrace(0, \"\")\n",
    "        return [x + middle + x[::-1] for x in answer]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
